package leetcode;

/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次 。
 * 返回同样按升序排列的结果链表。
 */
public class Test83_82_reverseList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.addIndex(0, 1);
        list.addIndex(1, 1);
        list.addIndex(2, 1);
        list.addIndex(3, 2);
        list.addIndex(3, 2);
        list.addIndex(3, 2);
        list.addIndex(6, 3);
        list.addIndex(7, 4);
        System.out.println(list);
//        removeToOnce(list.dummyNode.next);
        removeAll(list.dummyNode.next);
        System.out.println(list);

//        list.addIndex(0, 1);
//        list.addIndex(1, 2);
//        list.addIndex(2, 3);
//        list.addIndex(3, 4);
//        list.addIndex(4, 5);
//        System.out.println(list);
//        Node ret = reverseListSelf(list.dummyNode.next);
//        Node ret = reverseList(list.dummyNode.next);
//        Node ret = reverseTraversal(list.dummyNode.next);
//        Node ret = reverseNoNewSpace(list.dummyNode.next);
//        LinkedList list2 = new LinkedList();
//        list2.dummyNode.next = ret;
//        System.out.println(list2);
    }

    // 实现单链表逆转的方法
    /**
     *直接在原链表中通过改变各节点中的next关系直接逆转单链表
     * 没有开辟新的空间,空间复杂度为 O(1)
     * @param head
     * @return
     */
    public static Node reverseNoNewSpace(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node prev = head;
        Node cur = head.next;
        Node flag = null;
        head.next = null;
        while (cur != null) {
            flag = cur.next; // 使用flag记录cur的下一个节点
            cur.next = prev;
            prev = cur;
            cur = flag;
        }
        return prev;
    }

    /**
     * 创建一个新链表，边遍历原链表边将当前元素头插入新链表
     * 开辟了新的空间，空间复杂度为 O(N)
     * @param head
     * @return
     */
    public static Node reverseTraversal(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkedList list = new LinkedList();
        while (head != null) {
            list.addIndex(0, head.value);
            head = head.next;
        }
        return list.dummyNode.next;
    }

    /**
     * 利用递归求得头结点head对应链表的逆序，并返回新的头结点
     * 方法：使用head.next传入reverseList()传回逆序后的头结点
     * @param head
     * @return
     */
    public static Node reverseList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node secNode = head.next; // 标记一下第二个节点
        Node tmpNode = reverseList(head.next);
        secNode.next = head;
        head.next = null;
        return tmpNode;
    }

    /**
     * 利用递归求得头结点head对应链表的逆序，并返回新的头结点
     * 方法：遍历取最后一节点组成新链表
     * @param head
     * @return
     */
    public static Node reverseListSelf(Node head) {
        if (head == null || head.next == null) {
            return head;

        }
        // 遍历链表取最后一个节点
        Node tmpNode = head;
        Node prev = null;

        while (tmpNode.next != null) {
            prev = tmpNode;
            tmpNode = tmpNode.next;
        }
        Node ret = tmpNode;
        // 删除最后一个节点
        prev.next = null;
        ret.next = reverseList(head);
        return ret;
    }

    /**
     * 82：删除所有head对应的单链表中所有重复节点，并返回新头结点
     * @param head
     * @return
     */
    public static Node removeAll(Node head) {
        Node dummyNode = new Node(-1);
        dummyNode.next = head;
        Node prev = dummyNode;
        Node flag = head;
        Node cur = head.next;
        while (cur != null) {
            if (cur.value == flag.value) {
                while (cur != null && cur.value == flag.value) {
                    cur = cur.next;
                }
                flag = cur;
                prev.next = flag;
            } else {
                prev = prev.next;
                flag = flag.next;
            }
            cur = cur.next;
        }
        return dummyNode.next;
    }

    /**
     * 83:删除该头结点的所属单链表（按升序排序）的所重复的节点只保留一个
     * @param head
     * @return
     */
    public static Node removeToOnce(Node head) {
        Node dummyNode = new Node(-1);
        dummyNode.next = head;
        Node prev = dummyNode;
        Node cur = head;
        while (cur != null) {
            if (cur.value != prev.value) {
                prev.next = cur;
                prev = cur;
            }
            cur = cur.next;
        }
        prev.next = null;
        return dummyNode.next;
    }
}

class LinkedList {
    int size;
    Node dummyNode = new Node(-1); // 给虚拟头结点设置一个无效值

    /**
     * 在有虚拟头结点的单链表的任意索引位置添加节点
     * @param index
     * @param value
     */
    public void addIndex(int index, int value) {
        Node node = new Node(value);
        // 判断合法性
        if (index < 0 || index > size) {
            System.out.println("addIndex index is illegal!");
            return;
        }
        // 因为此链表中引入了虚拟头结点，元素插入在链表的任何位置都想当在中间插入
        Node prev = dummyNode; // 这里可以保证头结点不为空，不会引发空指针错误
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    /**
     * 用于判断修改和删除单链表节点时，索引的合法性
     * @param index
     * @return
     */
    private boolean isIllegal(int index) {
        if (index < 0 || index >= size) {
            System.out.println("Index is illegal!");
            return false;
        }
        return true;
    }

    /**
     * 用于修改任意索引处的值，并返回旧值
     * @param index
     * @param newValue
     * @return
     */
    public int modifyValue(int index, int newValue) {
        if (isIllegal(index)) {
            Node cur = dummyNode.next;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            int tmp = cur.value;
            cur.value = newValue;
            return tmp;
        }
        return -1;
    }

    /**
     * 用于删除任意索引处的节点
     * @param index
     */
    public void removeNodeIndex(int index) {
        if (isIllegal(index)) {
            Node prev = dummyNode;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            Node tmp = prev.next;
            prev.next = prev.next.next;
            tmp.next = null;
            size --;
        }
    }

    /**
     * 用于删除这个值第一次出现所对应的节点
     * @param value
     */
    public void removeValueOnce(int value) {
        Node prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.value == value) {
                Node tmpNode = prev.next;
                prev.next = prev.next.next;
                tmpNode.next = null;
                size --;
                return;
            }
            prev = prev.next;
        }
    }

    /**
     * 用于删除这个值相等的所对应的节点
     * @param value
     */
    public void removeValueAll(int value) {
        Node prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.value == value) {
                Node tmpNode = prev.next;
                prev.next = prev.next.next;
                tmpNode.next = null;
                size --;
            } else {
                prev = prev.next;
            }
        }
    }

    public String toString() {
        Node tmpNode = dummyNode;
        String str = "";
        while (tmpNode.next != null) {
            str += tmpNode.next.value + "->";
            tmpNode = tmpNode.next;
        }
        str += "NULL";
        return str;
    }
}

class Node {
    int value;
    Node next;
    public Node(int value) {
        this.value = value;
    }
}

